package LeetCode刷题;

import java.util.Arrays;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-25 18:53
 * @description: Functions of this class is
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 构造（小顶堆）  解法：时间复杂度为O（nlogk）
 * class Solution {
 *     public int findKthLargest(int[] nums, int k) {
 *         return sort(nums, k);
 *     }
 *
 *
 *     private int sort(int[] arr, int k) {
 *         //构建最大的K个值的小顶堆，
 *         int length = arr.length;
 *         int[] sort = new int[k];
 *         for (int l = 0; l < k; l++) {
 *             sort[l] = arr[l];
 *         }
 *         // 先构建最初的小顶堆
 *         for (int t = k / 2 - 1; t >= 0; t--) {
 *             //从第一个非叶子结点从下至上，从右至左调整结构
 *             adjustHeapSmall(sort, t, k);
 *         }
 *         // 其他元素录入
 *         for (int i = k; i < length; i++) {
 *             // 如果当前值 比 堆中最小值还小，那就continue
 *             if (sort[0] >= arr[i]) {
 *                 continue;
 *             } else {
 *                 // 否则替换掉重新排序
 *                 sort[0] = arr[i];
 *                 for (int j = k / 2 - 1; j >= 0; j--) {
 *                     //从第一个非叶子结点从下至上，从右至左调整结构
 *                     adjustHeapSmall(sort, j, k);
 *                 }
 *             }
 *         }
 *         return sort[0];
 *     }
 *
 *     public void adjustHeapSmall(int[] arr, int i, int length) {
 *         int temp = arr[i];//先取出当前元素i
 *         for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
 *             //从i结点的左子结点开始，也就是2i+1处开始
 *             // k用于获取当前i节点的两个子节点中较大的那一个
 *             // k+1<length 过滤的是仅有一个节点的情况
 *             if (k + 1 < length && arr[k] > arr[k + 1]) {//如果左子结点大于右子结点，k指向右子结点
 *                 k++;
 *             }
 *             // 如果子节点k 小于 父节点i，就先把父节点的值覆盖掉
 *             // 并且将K作为新的父节点  向下循环去查看是否有比k更小的子节点
 *             if (arr[k] < temp) {
 *                 arr[i] = arr[k];
 *                 i = k;
 *             } else {
 *                 break;
 *             }
 *         }
 *         // 当比较结束之后，把最初的temp中存储的父节点i的值赋给  更新后的i节点
 *         arr[i] = temp;
 *     }
 * }
 *
 *
 * 快速排序解法：时间复杂度O（n）：
 *
 * public static void main(String[] args) {
 *         Scanner sc = new Scanner(in);
 *
 *         String[] str = sc.nextLine().replace("[", "").replace("]", "").split(",");
 *
 *         int[] data = new int[str.length];
 *
 *         for (int i = 0; i < data.length; i++) {
 *             data[i] = parseInt(str[i]);
 *
 *         }
 *
 *         System.out.println(findKthNum(data, 3));
 *
 *         System.out.println(findKthNum1(data, 3));
 *
 *     }
 *
 * //方法1，基于快排思想的partion划分，时间复杂度O(n)，空间复杂度O(1)
 *
 *     public static int findKthNum(int[] data, int k) {
 *         int begin = 0, end = data.length - 1;
 *
 *         int pos = 0;
 *
 *         while (begin <= end) {
 *             pos = partion(data, begin, end);
 *
 *             if (pos == k - 1) {
 *                 return data[pos];
 *
 *             } else if (pos > k - 1) {
 *                 end = pos - 1;
 *
 *             } else {
 *                 begin = pos + 1;
 *
 *             }
 *
 *         }
 *
 *         return -1;
 *
 *     }
 *
 *     private static int partion(int[] data, int begin, int end) {
 *         int temp = data[begin];
 *
 *         while (begin < end) {
 *             while (begin < end && data[end] <= temp) {
 *                 end--;
 *
 *             }
 *
 *             swap(data, begin, end);
 *
 *             while (begin < end && data[begin] > temp) {
 *                 begin++;
 *
 *             }
 *
 *             swap(data, begin, end);
 *
 *         }
 *
 *         return begin;
 *
 *     }
 *
 *     public static void swap(int[] arr, int i, int j) {
 *         if (arr == null || i >= arr.length || j >= arr.length || i < 0 || j < 0) {
 *             return;
 *
 *         }
 *
 *         int temp = arr[i];
 *
 *         arr[i] = arr[j];
 *
 *         arr[j] = temp;
 *
 *     }
 *
 *
 *
 **/
public class No数组中第k个最大元素 {
    public static void main(String args[]){
        System.out.println(findKthLargest(new int[]{3,2,3,1,2,4,5,5,6},4));
    }
    public static int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}